package com.shuang.dp9;

class Solution {
    //转化为背包问题 每个元素只能用一次 所以是01背包 整个数组的元素和为sum的话 一旦找到其中有元素和为sum/2的话 剩下的元素和一定是sum/2 就一定可以分成两个子集满足题意
    //转换成01背包问题：背包容量为sum/2 数组中每个元素的数字既代表重量又代表价值 一旦能装满背包且背包最大价值为sum/2即满足题意
    public boolean canPartition(int[] nums) {

        //计算数组和
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1) {
            //和为奇数一定不满足
            return false;
        }

        //背包容量和装满时的最大价值都为sum/2
        int n = sum / 2;

        //定义dp数组 dp[j] 表示容量为j的背包最大价值为dp[j]
        int[] dp = new int[n + 1];

        //递归公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])

        //初始化 元素都是正整数 所以初始化为0即可 防止递推过程 最大值被初始值覆盖

        //遍历顺序 先物品前到后 在背包倒序遍历（避免物品重复加到背包中）
        for (int i = 0; i < nums.length; i++) {
            for (int j = n; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            //剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）
            if (dp[n] == n) {

                return true;
            }
        }

        return false;
    }
}